package algo;

import model.tsp.Problem;
import model.tsp.Solution;
import util.CheckUtils;
import util.PrinterUtils;

import java.util.List;
import java.util.TreeSet;

import static algo.Operator.*;
import static util.RandomUtils.randomNPoints;

public class VariableNeighborhoodSearch extends LocalSearch3 {


    public VariableNeighborhoodSearch(Problem problem) {
        super(problem);
    }

    public void solve() {
        Solution initSolution = initial();
        PrinterUtils.printTspResult("vns init", initSolution);
        Solution finalSolution = improve(initSolution);
        PrinterUtils.printTspResult("vns final", finalSolution);
        CheckUtils.check(finalSolution, distance);
        //plot(finalSolution);
    }


    @Override
    protected Solution improve(Solution solution) {
        return variableNeighborhoodDescent(solution);
    }


    // 变邻域搜索框架
    private Solution variableNeighborhoodDescent(Solution solution) {
        Solution bestSolution = solution.copy();
        Solution currentSolution = solution.copy();

        int kMax = 6;//邻域数量
        int epochs = 100;

        for (int epoch = 0; epoch < epochs; epoch++) {
            System.out.println("epoch = " + epoch);
            int k = 1;
            while (k <= kMax) {
                // shaking扰动
                Solution shakeSolution = shake(currentSolution.getPermutation(), k);

                // local search局部搜索
                Solution newSolution = localSearch(shakeSolution);

                // acceptance机制
                // 判断是否优于当前最优解
                if (newSolution.getCost() < currentSolution.getCost()) {
                    currentSolution = newSolution;
                    k = 1;
                    // 判断是否优于历史最优解
                    if (currentSolution.getCost() < bestSolution.getCost()) {
                        bestSolution = currentSolution.copy();
                        PrinterUtils.printTspResult("vns", bestSolution);
                    }
                } else {
                    k++;
                }
            }
        }

        return bestSolution;
    }

    private Solution shake(List<Integer> permutation, int type) {
        TreeSet<Integer> points = randomNPoints(2, permutation.size(), random);
        int first = points.first();
        int second = points.last();

        List<Integer> newPermutation;
        switch (type) {
            case 1:
                newPermutation = relocatedOperator(permutation, first, second);
                break;
            case 2:
                newPermutation = twoOptOperator(permutation, first, second);
                break;
            case 3:
                newPermutation = exchangeOperator(permutation, first, second);
                break;
            case 4:
                newPermutation = orOptOperator(permutation, first, second);
                break;
            case 5:
                newPermutation = rightShiftOperator(permutation, first, second, 1);
                break;
            default:
                newPermutation = leftShiftOperator(permutation, first, second,1);
        }

        int cost = calculateFitness(newPermutation);
        return new Solution(newPermutation, cost);
    }



}
